package com.example.leetcode;

/**
 * 动态规划 ** 参考题解
 * 最大子序和
 * 理解f(i)以i结尾的最大子序
 * 转移方程 f(i-1) +num[i] , num[i] 以i结尾的最大子序列
 */
public class Demo0053 {

    /**
     * dp
     * 边界 f(0)=nums[0],f(1)=max(f(0),f(0)+nums[1],nums[1]),
     * 转移方程 包含i的最大值f(i)=f(i-1)+num[i]与num[i]最大值
     * 维护一个最大值
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int preFun=nums[0];
        int maxVal=nums[0];
        for (int i = 1; i < nums.length; i++) {
            preFun=Math.max(preFun+nums[i],nums[i]);
            maxVal=Math.max(maxVal,preFun);
        }
        return maxVal;
    }
}
